#include "stdio.h"
#include "stdlib.h"

#define LIST_INIT_SIZE 100  //初始分配量
#define LISTINCREMENT 10  //分配增量

typedef int ElemType;

//数据对象
typedef struct {
	ElemType* elem;  //该线性表的基地址
	int length;  //当前线性表的长度
	int listsize;  //当前分配的存储容量
}SqList;

//初始化线性表
bool InitList_Sq(SqList& L) {
	L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));  //初始化空间
	if (!L.elem) return false;  //判断初始化空间是否成功
	L.length = 0;  //初始长度为0
	L.listsize = LIST_INIT_SIZE;  //线性表分配空间长度
	return true;
}

//线性表中插入元素
bool ListInsert_Sq(SqList& L, int i, int num) {
	if (i<1 || i>L.length + 1) return false;
	if (L.length > L.listsize) {  //存储空间已满，分配增量
		ElemType* newspace = (ElemType*)realloc(L.elem,(L.listsize + LISTINCREMENT) * sizeof(ElemType));
		if (!newspace) return false;
		L.elem = newspace;  //重新赋值基地址
		L.listsize = L.listsize + LISTINCREMENT;  //改变存储容量
	}
	ElemType* p = &L.elem[i - 1];  //下标为i-1的地址
	for (ElemType* q = &L.elem[L.length - 1]; q >= p; q--)
		*(q+1) = *q;  //从length - 1 到 i - 1 进行移位操作
	*p = num;  //将值赋给下标地址
	L.length++;  //线性表长度+1
	return true;
}

//线性表中删除元素
bool ListDelete_Sq(SqList& L, int i, ElemType& e) {
	if (i<1 || i>L.length + 1) return false;
	ElemType* p = &L.elem[i - 1];  //删除元素的地址
	e = *p;  //将删除元素赋值给e
	p = &L.elem[i];
	for (ElemType* q = &L.elem[L.length - 1]; p <= q; p++)
		*(p - 1) = *p;  //从i到legnth-1开始往前移位操作
	L.length--;
	return true;
}

//查找线性表中的元素
int LocateElem_Sq(SqList L, ElemType e) {
	int i = 1;  //返回下标
	ElemType* p = &L.elem[0];  //从第一个元素开始遍历
	while (i <= L.length && *p++ != e) ++i;  //如果没遍历到头，*p与e不相同，则继续遍历
	if (i <= L.length) return i;
	else return 0;
}

//输出线性表
void Print_Sq(SqList L) {
	for (int i = 0; i < L.length; i++) {
		printf("%3d", L.elem[i]);
	}
	printf("\n");
}

int main() {
	SqList L;  //定义一个线性表
	ElemType e;  //接受删除的参数
	InitList_Sq(L);  //初始化线性表
	//插入
	ListInsert_Sq(L, 1, 1);
	ListInsert_Sq(L, 1, 2);
	ListInsert_Sq(L, 1, 3);
	ListInsert_Sq(L, 1, 4);
	ListInsert_Sq(L, 1, 5);
	ListInsert_Sq(L, 3, 6);
	ListInsert_Sq(L, 7, 7);
	Print_Sq(L);
	//删除
	if (ListDelete_Sq(L, 7, e)) {
		printf("%3d\n", e);
	}
	if (ListDelete_Sq(L, 3, e)) {
		printf("%3d\n", e);
	}
	if (ListDelete_Sq(L, 1, e)) {
		printf("%3d\n", e);
	}
	Print_Sq(L);
	//查找
	int x = LocateElem_Sq(L, 2);
	printf("2的位置为：%3d", x);
	return 0;
}